package mianshi.huawei.medium;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/*
功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
最后一个数后面也要有空格
输入描述:
输入一个long型整数
输出描述:
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。
示例1
输入
180
输出
2 2 3 3 5
 */
public class 质数因子 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String next = scanner.next();
            tset(Long.parseLong(next));
        }



    }

    public static void tset(long num) {
        List<Integer> list = new ArrayList<>();
        setList(num, list);
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        Arrays.sort(arr);
        for (int i : arr) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public static void setList(long num, List<Integer> list) {
        for (int i = 2; i <= num; i++) {
            //判断是否是质数因子
            if (isPri(i) && num % i == 0) {
                list.add(i);
                num = num / i;

            }
        }
        if (num != 1) {
            setList(num, list);
        }
    }

    /**
     * 判断是否是质数
     * @param num
     * @return
     */
    private static boolean isPri(long num) {
        if (num <= 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        boolean flag = true;
        //遍历到num的平方根,并且忽略2的倍数,如果没被整除,说明是质数,
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                flag = false;
            }
        }

        return flag;
    }

}
